#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <time.h>
#include <math.h>
#include <ctype.h>
#include <sys/time.h>
#include "rede.h"






/*****************************************************************************************/
/* Funcao: LeMatriz									*/
/* Descricao: Leitura do arquivo pasado como paramento. 				*/
/*	     O arquivo deve conter: n<int> indicado o ordem das matrizes, uma linha     */
/*	     vazia, a matriz de adjacencias, uma linha vazia e a matriz de trafego.	*/
/****************************************************************************************/
void LeMatriz(char *instancia){
FILE* Mat;
int i, j;

        Mat = fopen(instancia, "r");

        fscanf(Mat, "%d ",&n);
        fscanf(Mat,"\n");

  /* Le a matriz de distancia(adjacencia) */

	for(i = 0; i < n; i++){
                for(j = 0; j < n; j++){
                        fscanf(Mat, "%d ", &E[i][j]);
						dist[i][j] = E[i][j];
						if (dist[i][j]==0 && i!=j) dist[i][j]=9999; // caso o nodo i tenha distancia zero do nodo j, atribui 9999. (J)
		}
	}

        fscanf(Mat, "\n");

 /* Le matriz de trafego */

	for(i = 0; i < n; i++){
                for(j = 0; j < n; j++){
                        fscanf(Mat, "%d ", &traf[i][j]);
		}
	}


	fclose(Mat);
}


/****************************************************************************************/
/* Funcao: convertearquivo								*/
/* Descricao: Converte as matrizes de trafego e adjacencias para o forma de entrada do  */
/* algoritmo de YEN implementado pelo Celio. O arquivo gerado sera posteriormento apagado	*/
/****************************************************************************************/
int convertearquivo(){
int i,j;
FILE *str;


	if((str = fopen("lixo2", "w")) == NULL){
		printf("Nao foi possivel alocar memoria!!!\n\n");
		exit(1);
	}
	
	fprintf(str,"O Celio mandou escrever essa linha inutil\n");
	for(i = 0; i < n; i++){
    	for(j = 0; j < n; j++){
			if(E[i][j]!=0){ //matriz de distancia
            	fprintf(str," %d  %d  1  1.0\n",i,j);
			}
		}
	}

	fclose(str);

return 0;
}



/****************************************************************************************/
/* Funcao: ArqRotas									*/
/* Descricao: Executa o algoritmo de YEN para todo os pares s-d				*/
/****************************************************************************************/
int ArqRotas(){
int i,j,aux=N_ROTAS_YEN;
char str[50];

        for(i=0;i< n;i++){
			for(j=0;j< n;j++){
				if(i!=j){
					sprintf(str,"./ksp lixo2 %d %d %d >> lixo",i,j,aux); //arquivo de leitura, saida, destino, numero_rotas_yen (para chamar no terminal)
					system(str);
				}
			}
       	}
return 0;
}
/****************************************************************************************/
/* Funcao: lerEanalisar01								*/
/* Descricao: Le o arquivo de saida o algoritmo de Yen e converta para uma matriz  	*/
/* M[fonte][destino][identificador da rota][indice para precorrer os caminhos]		*/
/****************************************************************************************/
int lerEanalisar01(){
FILE *inst;//,*str;
int percorretexto=0,tamanhopalavra=0,lixopalavra,percorreplv,del;
int marc1=0,marc2=0,marc3=0,s,d,aux1=0,aux2=0,cont=0,percorrevet=0;

int i,j,t,k;//lixo

	inst = fopen("lixo","r");
	
	for (percorretexto=0;;percorretexto++){
		fscanf(inst,"%c",&texto[percorretexto]);
		palavra[tamanhopalavra] = texto[percorretexto];

		/* Quebra a frase em palavras */
		if (texto[percorretexto] == ' ' || texto[percorretexto] == '\0' ){

			/* Removo o lixo que possa existir no restante da "palavra". */
			for(lixopalavra=tamanhopalavra ; lixopalavra<TAMANHO_PALAVRA;lixopalavra++ ){
				palavra[lixopalavra] = '\0';
			}

			for(percorreplv=0;percorreplv<=tamanhopalavra;percorreplv++){

				if((palavra[percorreplv]=='D') && (palavra[percorreplv+1]=='e')){
					marc1=1; cont=0;
				}
				if((palavra[percorreplv]=='p') && (palavra[percorreplv+1]=='a')){
					marc2=1;
				}
				
				if((marc1==1) && (isdigit(palavra[percorreplv]))){ /*isdigit verifica se eh numero, se for, 
																	return !=0, caso contrario retorna 0 (J)*/
					aux1=(int)(palavra[percorreplv] - '0');
					if(palavra[percorreplv+1]!='.'){
						aux2=aux1*10;
						aux1=(int)(palavra[percorreplv+1] - '0');
					}
					s=aux1+aux2;
					//if(n<s)n=s;//????
					aux1=aux2=0;
					marc1=0;
					marc3=0;
					
				}
				if((marc2==1) && (isdigit(palavra[percorreplv]))){
					aux1=(int)(palavra[percorreplv] - '0');
					if(palavra[percorreplv+1]!='.'){
						aux2=aux1*10;
						aux1=(int)(palavra[percorreplv+1] - '0');
					}
					d=aux1+aux2;
					aux1=aux2=0;
					marc2=0;
				}
				if((palavra[percorreplv]=='a') && (palavra[percorreplv+1]==':')){
					cont++;
					marc3=1;
				}

				if(palavra[percorreplv] == ';') { marc3=0; percorrevet=0;}
				if((marc3==1) && (isdigit(palavra[percorreplv]))){
					
					aux1=(int)(palavra[percorreplv] - '0');
					if(palavra[percorreplv+1]!='.'){
						aux2=aux1*10;
						aux1=(int)(palavra[percorreplv+1] - '0');
						percorreplv++;
					}
					del=aux1+aux2;
					aux1=aux2=0;
					
					M[s][d][cont-1][percorrevet]=del; //preenche as rotas
					M[s][d][cont-1][percorrevet+1]=-1;
					
					percorrevet++;
					aux1=aux2=0;
//					printf("foi %d %d\n",s,d);
				}
			}
		tamanhopalavra = 0;
		
		}
		else tamanhopalavra++;
		if (texto[percorretexto] == '\0') break;
		
	}
		
	fclose(inst);
	return 0;
}

/****************************************************************************************/
/* Funcao: mostratudo()									*/
/* Descricao: Mostra todas as rotas de todos os pares s-d				*/
/****************************************************************************************/
int mostratudo(){
int i,j,k,t,nr=N_ROTAS_YEN;
	/*Imprime uma matriz de quatro dimensoes */
	for(i=0;i<n;i++){
		for(j=0;j<n;j++){
			if(i!=j){ // dois loops acima para rodar a saida e destino apenas
				printf("s = %d | d = %d\n",i,j); //saida e destino da rota
				for(t=0;t<nr;t++){  // loop de t e k para imprimir rota YEN e nos
					for(k=0;k<=n;k++){
// 						if(M[i][j][t][k]==-1)break;
						printf("%d ",M[i][j][t][k]);
					}
				printf("\n");
				} 
				printf("\n\n");
			}
		}
	}
}



///////////////////////////////////////////////////////////////////////////////////////////
/****************************************************************************************/
/* Funcao: ContaSaltos																	*/
/* Descricao: função que conta o número de salto da rota t atendendo a demanda sd		*/
/****************************************************************************************/
int contaSaltos(int s,int d,int t){
int k,aux=-1;

	for(k=0;k<=n;k++){
		if(M[s][d][t][k]==-1)break; 
		aux++;
	}
	return aux;
}



void imprimeMatriz(int ** matriz, int linha, int coluna){
	
	int i, j;
	
	for(i=0; i<linha; i++){
		for(j=0; j<coluna; j++){
			printf("%d\t", matriz[i][j]);
			}
		printf("\n");
	}

}

int descobreNumLinks(void)
{
	int i, j, numero=0;
	for(i=0; i<TAMANHO_n; i++){
		for(j=0; j<TAMANHO_n; j++){
			if(E[i][j]==1) numero++;
		}
	}
	return numero;
}



Rede ** alocaRede(void)
{

	Rede ** rede;
	int i;
	
	rede=(Rede**)malloc(n*sizeof(Rede*));
	if (rede==NULL) exit(1);
	
	for(i=0; i< n; i++){
		rede[i]=(Rede*)malloc(n*sizeof(Rede));
		if(rede[i]==NULL) exit(1);
	}
	
	return rede;



}


void recebeDemanda( Rede ** rede)
{
	int i,j;
	
	for(i=0; i< TAMANHO_n; i++)
	{
		for(j=0; j< TAMANHO_n; j++)
		{
			
			rede[i][j].demanda=traf[i][j];
			rede[i][j].w=9999;	
			
		}
	}
}
	

void imprimeDemanda ( Rede ** rede)
{
	int i,j;
	for(i=0; i< TAMANHO_n; i++)
	{
		for(j=0; j<TAMANHO_n; j++)
		{
			printf("Demanda[%d][%d]: %d\n", i,j, rede[i][j].demanda);
		}
	}


}

// void imprimeRedeSolucao(Solucao sol){
	// int i,j;
	
	// for(i=0; i< TAMANHO_n; i++)
	// {
		// for(j=0; j<TAMANHO_n; j++)
		// {
			// if(i!=j && sol.rotas[i][j].demanda>0){
				// printf("Demanda/Rota/Frequencia[%d][%d]: %d/%d/%d\n", i,j, sol.rotas[i][j].demanda,sol.rotas[i][j].rota,sol.rotas[i][j].w);
				// }
		// }
	// }


// }

// RNET sera uma matriz ou uma estrutura com s,d dentro???

RNET ** alocaMatrizRNET(void)
{

	int i;
	RNET ** rnet;
	
	rnet=(RNET**)malloc(n*sizeof(RNET*));
	if(rnet==NULL) exit(1);
	
	for(i=0; i<n; i++)
	{
		rnet[i]=(RNET*)malloc(n*sizeof(RNET));
		if(rnet[i] ==NULL) exit(1);
	}
	
	return rnet;
}

void alocaVetorSlots(RNET ** rnet)
{
	int i, j,k;
	
	for(i=0; i<n; i++)
	{
		for(j=0; j<n; j++)
		{
			rnet[i][j].slots=(int*)calloc(NUM_SLOTS, sizeof(int));
		}
	}


}


int contaZeroSequencial( int *v, int traf, int * freq)
{
	int i, num_zeros=0;
	//traf eh o trafego de [i][j] (saida e destino originais)
	// v eh o vetor de slots
	//freq eh um ponteiro pra pegar o indice da freq no vetor de slots;
	if(*freq==9999) i=0;
	else i=*freq;
	for(; i<NUM_SLOTS; i++)
	{
		
		if(v[i]==0)
		{
			
			if(*freq==9999) *freq=i;
			else if(*freq!=9999 && num_zeros==0) *freq=i;
			num_zeros++;
		}
		
		else
		{
			if(num_zeros>=traf) return num_zeros;
			else num_zeros=0;
		}
	}

	if(num_zeros>=traf) return num_zeros;
	//else return 0;
			

}


int calculaRota(RNET ** rnet, int i, int j, int *freq)
{
	//como calcular a rota?
	int  aux,zeros,k;
	int rota, flag;
	
	
	
	
	for(rota=0; rota< N_ROTAS_YEN; rota++)
	{
		*freq=9999; //ISSO EH PRA SER MAIS TESTADO, FUNCIONAVA SEM APAGAR, MAS ELE OTIMIZA (CASO FUNCIONE)
		flag=0; //caso seja 0 no final eh pq existe espaco naquela rota
		k=0;
		while(k<n)
		{
			aux=*freq;
			//printf("Aux %d\n", aux);
			if(M[i][j][rota][k] == 0 && M[i][j][rota][k+1]==0){ //acabaram as rotas e nao achou
				return 9999;
			}
			
			if(M[i][j][rota][k+1]==-1) break;
			zeros=contaZeroSequencial(rnet[M[i][j][rota][k]][M[i][j][rota][k+1]].slots, traf[i][j], freq);
			//printf("%d para %d\tFREQUENCIA NA FUNCAO: %d ROTA: %d\n", M[i][j][rota][k],M[i][j][rota][k+1],*freq,rota);
			if(*freq!=aux)
			{
				k=0;
				continue;
			}			
			
			if(zeros<traf[i][j])
			{
				flag=1;
				break;
			}
			k++;
			
		}
		if (flag==0) return rota;
	}
	
	
	return 9999;

}	
		

void imprimeRNET( RNET ** rnet, int valor)
{

	FILE * teste;
	int i,j,k;
	teste=fopen("RecursoRede6NosTesteJoao.txt", "w");
	if(teste == NULL) exit(1);
	
	for(i=0; i<n; i++)
	{
		for(j=0; j<n; j++)
		{
				fprintf(teste,"\t\tLINK DIRETO I[%d] J[%d]\n", i, j);

				for(k=0; k<NUM_SLOTS; k++)
				{
					fprintf(teste,"%d ", rnet[i][j].slots[k]);
				}
				fprintf(teste,"\n");
			
		}
	}
}



No * inicializa(){
	return NULL;
}
void erro(){
	printf("Espaco nao foi alocado");
	exit(1);
}

int ** alocaMatriz(){
	int ** mat;
	int i;
	
	mat=(int**)malloc(n*sizeof(int*));
	if(mat==NULL)
		erro();
	for(i=0; i<n;i++){
		mat[i]=(int*)malloc(n*sizeof(int));
		if(mat[i]==NULL)
			erro();
	}
	
	return mat;
	
}	
int ** alocaMatrizZerada(){
	int ** mat;
	int i,j;
	
	mat=(int**)malloc(n*sizeof(int*));
	if(mat==NULL)
		erro();
	for(i=0; i<n;i++){
		mat[i]=(int*)malloc(n*sizeof(int));
		if(mat[i]==NULL)
			erro();
	}
	for(i=0;i<n;i++){
		for(j=0;j<n;j++){
			mat[i][j]=0;
		}
	}
	
	return mat;
	
}	

void insereNodo(Lista * l, No * novo){ //Insere no final da lista
	
	No * aux;
	if(l->tam==0){
		l->ini=l->fim=novo;
		l->tam++;
	}
	
	else if((novo->peso) > (l->ini->peso)){
		novo->prox=l->ini;
		l->ini=novo;
		l->tam++;
		
	//printf("ENTROU 3\n");
	}
	
	else if((novo->peso) <= (l->fim->peso)){
		l->fim->prox=novo;
		l->fim=novo;
		l->tam++;
		
	//printf("ENTROU 4\n");
	}
	
	else{
		
		
		for(aux=l->ini;aux!=l->fim; aux=aux->prox){
			if(aux->prox->peso < novo->peso){
				novo->prox=aux->prox;
				aux->prox=novo;
				l->tam++;
				break;
			}
		}
	}
	
}

void roleta(int * s, int * d){ // roleta probabilistica

	int t=0,aux=N_ROTAS_YEN;
	//int seed;
	long sec;


	struct timeval tv;      //gera variaveis aleatorias com tempo em microsegundos
	unsigned int seed;
	while(*s==*d){
			gettimeofday(&tv,0);
			seed=(tv.tv_usec);
			srand(seed);
			*s=(0 + rand() % n);     //seleciona fonte

			gettimeofday(&tv,0);
			seed=(tv.tv_usec);
			srand(seed);
			*d=(0 + rand() % n);     //seleciona destino
	}
}


void roleta2(int *s, int * d, int tam){
	int t=0,aux=N_ROTAS_YEN;
	//int seed;
	long sec;
	int numero;
	numero=tam;
	printf("Procura sol random\n");
	struct timeval tv;      //gera variaveis aleatorias com tempo em microsegundos
	unsigned int seed;
	
	*s=*d=0;
	while(*s==*d){
		printf("Loop da procura\n");
			gettimeofday(&tv,0);
			seed=(tv.tv_usec);
			srand(seed);
			*s=(0 + rand() % numero);     //seleciona fonte

			gettimeofday(&tv,0);
			seed=(tv.tv_usec);
			srand(seed);
			*d=(0 + rand() % numero);     //seleciona destino
	}
	
}

int calculaPeso(int s, int d, int demanda){
	int saltos, peso;
	saltos=contaSaltos(s,d,0);
	
	peso=demanda * saltos;
	
	return peso;
}

int calculaPesoFitness(int s, int d, int demanda,int caminho){
	int saltos;
	int peso;
	saltos=contaSaltos(s,d,caminho);
	
	peso=demanda * saltos;
	
	return peso;
}


Lista * recebeRecurso(Lista * l){
	
	int i,j;

	
	for(i=0; i< n; i++){
		for(j=0; j<n; j++){
			if(i!=j && traf[i][j]>0){ //verifica se existe de demanda
				//printf("AQUI4\t");
				No * novo;
				novo=(No*)malloc(sizeof(No));
				novo->prox=NULL;
				novo->s=i;
				novo->d=j;
				novo->peso=calculaPeso(i,j,traf[i][j]);
				novo->demanda=traf[i][j];
				
				
				insereNodo(l, novo);
			}
			
		}
	}
	return l;
	
}

void imprimeLista(Lista * l){
	No * aux;
	
	for(aux=l->ini; aux!=NULL; aux=aux->prox){
		printf("Saida: %d\tDestino: %d\tPeso: %d  Demanda: %d\n", aux->s, aux->d, aux->peso, aux->demanda);
	}
	
}

int calculaRotaUnica(RNET ** rnet, int i, int j, int *freq, int rota)
{
	int aux,zeros,k;
	int flag;
	
	
	
	
	
		flag=0; //caso seja 0 no final eh pq existe espaco naquela rota
		k=0;
		while(k<n)
		{
			aux=*freq;
			//printf("Aux %d\n", aux);
			if(M[i][j][rota][k] == 0 && M[i][j][rota][k+1]==0){ //acabaram as rotas e nao achou
				return 9999;
			}
			
			if(M[i][j][rota][k+1]==-1) break;
			zeros=contaZeroSequencial(rnet[M[i][j][rota][k]][M[i][j][rota][k+1]].slots, traf[i][j], freq);
			//printf("%d para %d\tFREQUENCIA NA FUNCAO: %d ROTA: %d\n", M[i][j][rota][k],M[i][j][rota][k+1],*freq,rota);
			if(*freq!=aux)
			{
				k=0;
				continue;
			}			
			
			if(zeros<traf[i][j])
			{
				flag=1;
				break;
			}
			k++;
			
		}
		if (flag==0) return rota;

	
	
	return 9999;

}	

int calculaRotaRandom( RNET ** rnet, int ** qtdRotas, int i, int j, int *freq, int * contaRotaZero, int valorListaTaxada){
	
	int route,achou;
	int teste;
	teste=*freq;
	//printf("FREQ %d ", *freq);
	if((*contaRotaZero)	<valorListaTaxada){
		(*contaRotaZero)++;
		route=0;
		//printf("CONTAROTAZERO: %d \t ListaTaxada: %d\n", *contaRotaZero, valorListaTaxada);
	}
	else{
		route=rand()%qtdRotas[i][j];
		//printf("Rota Random: %d\n", route);
		
	}
	achou=calculaRotaUnica(rnet, i,j,freq,route);
	printf("Achou Rota: %d\n", achou);
	if(achou==9999){
		//printf("achou entrou aqui\n");
		achou=calculaRota(rnet, i,j,&teste);
		*freq=teste;
		printf("ACHOU Rota2: %d\n", achou);
	}
	
	return achou;
}



void zeraMatriz(int ** mat, int l, int c){
	int i,j;
	
	for(i=0; i<l; i++){
		for(j=0; j<c; j++){
			mat[i][j]=0;
		}
	}
}



	
int comparaRede(Rede ** m1, Rede ** m2, int numNodos) // l = num de linhas e c = num de colunas
{
	// nesse caso eu quero que elas sejam diferentes, se forem iguais retorna zero
	int i,j;
	
	for ( i = 0; i < numNodos ; i++){
		for ( j=0 ; j <numNodos; j++){
			if(m1[i][j].rota!=m2[i][j].rota) return 1; //se forem diferentes, retorna verdadeiro
		}
	}
	
	return 0;

}	

void liberaRnet(RNET ** rnet){
	int i,j;
	//printf("TESTE 7\n");
	for(i=0; i< TAMANHO_n ; i++){
		for(j=0 ; j<TAMANHO_n; j++){
			free(rnet[i][j].slots);
		}
	}
	//printf("TESTE 8\n");
	for(i=0 ; i< TAMANHO_n; i++){
		free(rnet[i]);
	}
	//printf("TESTE 9\n");
	free(rnet);
}

void liberaMatriz(int ** mat, int tam){
	int i;
	//printf("TESTE 5\n");
	for(i=0; i< tam; i++){
		free(mat[i]);
	}
	//printf("TESTE 6\n");
	free(mat);
}

	
double randomico(double min, double max)
{
	//srand(time(NULL));
	return ((double)(rand()%10000)/10000.0)*(max-min)+min;
}

int irandomico(int min, int max)
{
	return (int)randomico(0,max-min+1.0) + min;
}

void matrizQtdRotas(int ** qtdRotas){
	
	
	int i,j,k,y;
	y=0;
	//printf("ENTROU\n");
	
	for(i=0; i<n; i++){
		
		for(j=0; j<n; j++){
			
			for(k=0; k<N_ROTAS_YEN; k++){
				if((M[i][j][k][y]==0) && (M[i][j][k][y+1]==0)) break;
				else{
					qtdRotas[i][j]++;
				}
					
				
			}
		}
	}
}



